
\begin{exercise}
   Let $(G,s,t,c)$ be a flow network and $V_0, V_1, \dots, V_k$ be an optimal layering
   (that is, $k = {\rm dist}_G(s,t)$.
   Let $p$ be a path from $s$ to $t$ of length $k$. 
   Suppose we route some flow $f$ along $p$ (of some
   value $c_{\rm min} > 0$) and let $(G_f,s,t,c_f)$ be the residual network. Show that
   $V_0, V_1,\dots, V_k$ is a layering of $(G_f,s,t,c_f)$, too. Obviously, condition (1) and (2) in
   the definition of $k$-layerings still hold, so you only have to check  condition (3).
\end{exercise}

\textbf{Solution}

For any edge $(u,v)$ in path $p$ in $G$, $u \in V_i$, $v \in V_j$, $j \leq i + 1$.

Since the length of the path is $k$, $j = i + 1$

In the residual graph $G_f$, $(u,v)$ split to $(u,v)$ and $(v,u)$.

Obviously, $(u,v)$ still satisfies the condition (3).

For $(v,u)$, $i = j-1 \leq j+1$, thus it satisfies the condition (3), too.

Therefore, $V_0, V_1, \dots, V_k$ is a layering of $(G_f, s, t, c_f)$, too.


\begin{exercise}
   Show that every network $(G,s,t,c)$ has an optimal layering, provided there is a path
   from $s$ to $t$.
\end{exercise}

\textbf{Solution}

\textbf{Case 1}: When the provided path from $s$ to $t$ is the shortest-path with length $k$, according to \textbf{Exercies 10.5}, there is a $k$-layering. Thus, the network has an optimal layering.

\textbf{Case 2}: When the provided path from $s$ to $t$ is not the shortest-path, then there is another shortest-path from $s$ to $t$ with length $k$. According to \textbf{Exercies 10.5}, there is a $k$-layering. Thus, the network has an optimal layering.


\begin{exercise}
   Imagine we are in some iteration of the while-loop of the Ford-Fulkerson method.
   Let $V_0, \dots, V_k$ be an optimal layering of $(G,s,t,c)$. Show that after at most $m$
   iterations of the while-loop, $V_0,\dots,V_k$ ceases
   to be an optimal layering. \textbf{Remark.} Note that it is the {\em network} that changes from
   iteration to iteration of the while-loop, not the partition $V_0,\dots,V_k$. We consider
   the partition $V_0,\dots,V_k$ to be fixed in this exercise.
\end{exercise}

\textbf{Solution}

After every iteration, an edge is completely reversed. Note that the reversed edge cannot appear in the shortest path again becauce it "goes back" to lower layer.

When the edge $(u,v)$ is reversed to $(v,u)$, the chosen path $s \rightarrow \dots u \rightarrow v \rightarrow \dots t$ no longer exists. And the algorithm choose the shortest path, so the chosen path is the shortest path and the reversed edge is part of the shortest path, namely the edge crossing the layers. There may be many shortest paths. And there are at most $m$ edges crossing the layers, so after at most $m$ iterations, all the edges of the original shortest paths is reversed and the new shortest paths have a longer length. So $V_0, V_1, \dots, V_n$ ceases to be an optimal layering.
